package com.cat.dynamicPlanning02;

/**
 *   @description https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
 *   @author 曲大人的喵
 *   @create 2025/10/17 19:28
 *   @since JDK17
 */

public class Solution21 {
    public int maxProfit(int[] prices) {
        int n = prices.length, ans = 0;
        int[] dp1 = new int[n], dp2 = new int[n], best = new int[n];
        // dp1[i] : 在0 - i之间做一次交易，最多能获得多少收益
        for (int i = 1, min = prices[0]; i < n; i++) {
            dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        best[0] = -prices[0];
        for (int i = 1; i < n; i++) {
            best[i] = Math.max(best[i - 1], dp1[i] - prices[i]);
        }

        for (int i = 1; i < n; i++) {
            dp2[i] = best[i] + prices[i];
//            for (int j = 1; j <= i; j++) {
//                dp2[i] = Math.max(dp2[i], dp1[j] + prices[i] - prices[j]);
//            }
            ans = Math.max(ans, dp2[i]);
        }

        return ans;
    }
}
